<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<meta name="keywords" content="spring,Spring,java,web,程序员,博客,IT,技术,移动开发,Web前端,企业架构,编程语言,互联网,数据库,技术博客,blog,分布式架构,分布式">
		<meta name="description" content="cdcoder是一个程序员学习交流平台，深度IT技术博客，移动开发博客,Web前端博客,企业架构博客,编程语言博客,互联网博客,数据库博客,IT blog,核心关注IT知识传播，共享。为更好的IT产业贡献一份微薄的力量。">
		<link rel="shortcut icon" href="/img/code.ico" />
		<link rel="bookmark"href="/img/code.ico" />
		<title>限流相关知识</title>
		<link href="/css/index.css" rel="stylesheet">
		<link href="/css/github.css" rel="stylesheet" />
		<style>
			body {
				font-size: 16px;
				font: 400 16px/1.62 Georgia, "Xin Gothic", "Hiragino Sans GB", "Droid Sans Fallback", "Microsoft YaHei", sans-serif;
				font-family: 'PT serif', 微軟正黑體, 微软雅黑, 华文细黑, Microsoft Yahei, Hiragino Sans GB, sans-serif;
				color: #D0CCCC;

				text-shadow: 0px 0px 1px rgba(24, 22, 22, 0.35);
				background-color: #000;
			}
			p{ text-indent:2em; padding:0px; margin:0px; }
		</style>
	</head>
	<body>

		<header>
			<div class="logo"><a href="/index.html">徐思润博客</a></div>
		<nav>
			<ul id="starlist">
				<li><a href="/java/index.html">java</a></li>
				<li><a href="/data/index.html">算法与数据结构</a></li>
				<li><a href="/db/mysql.html">数据库</a></li>
				<li><a href="/distribution/index.html">分布式</a></li>
				<li><a href="/framework/index.html">架构</a></li>
				<li><a href="/interview/index.html">面试与被面试</a></li>
				<li><a href="/live/index.html">日常生活</a></li>
				<li><a href="/about.html">关于我</a></li>
				<li><a href="/baby/index.html">baby墙</a></li>
			</ul>
		</nav>
		</header>
		<div class="box">
			<h1 style="text-align: center;">限流的原理与实现</h1>
			<h2>限流算法</h2>
			<h3>计数器算法</h3>
				<p>计数器算法为最简单的算法，该算法维护一个counter，规定时间内counter的值不能超过最大值，每隔一段时间就将counter的值清零，如果这个counter的值大于了阈值，就拒绝后面的请求
				丢弃或者等待以保护系统的负载</p>
				<p>实现代码<p>
					<pre><code data-language="java">
				 private Long maxReq;//最大请求数
				private Integer timer;//过期时间 单位是秒
				private LimitType type;//限流的类型
				ConcurrentHashMap&lt;String,Long&gt; concurrentHashMap=new ConcurrentHashMap();   //记录数据
				
				DelayQueue&lt;Limiter&gt; delayQueue=new DelayQueue&lt;Limiter&gt;();//过期设置  不依赖redis
				
				public void init(Long max,Integer timer ,LimitType type){
					this.maxReq=max;
					this.timer=Objects.isNull(timer)?60:timer;
					this.type=type;
					run();
				}
				public  Boolean hasNext(String linmit){
					String key=this.type.name()+linmit;
					Long i = concurrentHashMap.get(key);
					if(Objects.isNull(i)){
						delayQueue.add( Limiter.builder().executeTime(timer).key(key).build());
					}
				   i=Objects.isNull(i)?new AtomicLong().incrementAndGet():new  AtomicLong(i).incrementAndGet();
					return i &lt; maxReq ; 
	}
					public void run() {
						while (true) {
							try {
								Limiter take = delayQueue.take();
								if(Objects.nonNull(take)){
									concurrentHashMap.remove(take.getKey());
								 }
							} catch (InterruptedException e) {
								e.printStackTrace();
							}
						}
					}
	</code></pre>
							<pre><code data-language="java">
					@Data
					@Builder
					public class Limiter   implements Delayed {
						private long executeTime;
						private String key;
						@Override
						public long getDelay(TimeUnit unit) {
							return unit.convert(this.executeTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
						}
						@Override
						public int compareTo(Delayed o) {
							return (int) (this.getDelay(TimeUnit.MILLISECONDS) - o.getDelay(TimeUnit.MILLISECONDS));
						}
					}

				</code></pre>
			 <h3>漏桶</h3> 
			 <img src="https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/e731dd66d649223a49b9fa0060a98bff1d3d1cfc538f382daa087c8258573eb45b4733047e7f095498c2fb4380925e99?pictype=scale&from=30113&version=3.3.3.3&uin=182478932&fname=2184951-073c2f46582d1ad2.webp.jpg&size=750" />
				<p>
			为了消除"突刺现象"，可以采用漏桶算法实现限流，漏桶算法这个名字就很形象，算法内部有一个容器，类似生活用到的漏斗，当请求进来时，相当于水倒入漏斗，然后从下端小口慢慢匀速的流出。
			不管上面流量多大，下面流出的速度始终保持不变。</p>
			<p>不管服务调用方多么不稳定，通过漏桶算法进行限流，每10毫秒处理一次请求。因为处理的速度是固定的，请求进来的速度是未知的，可能突然进来很多请求，没来得及处理的请求就先放在桶里，既然是个桶，
			<p>肯定是有容量上限，如果桶满了，那么新进来的请求就丢弃。</p>
			在算法实现方面，可以准备一个队列，用来保存请求，另外通过一个线程池（ScheduledExecutorService）来定期从队列中获取请求并执行，可以一次性获取多个并发执行。</p>
					
				<p>这种算法，在使用过后也存在弊端：无法应对短时间的突发流量。
			</p>
				
			<h3>令牌桶</h3>
			<p> 令牌桶算法是对漏桶算法的一种改进，桶算法能够限制请求调用的速率，而令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用。
在令牌桶算法中，存在一个桶，用来存放固定数量的令牌。算法中存在一种机制，以一定的速率往桶中放令牌。每次请求调用需要先获取令牌，只有拿到令牌，才有机会继续执行，否则选择选择等待可用的令牌、或者直接拒绝。
放令牌这个动作是持续不断的进行，如果桶中令牌数达到上限，就丢弃令牌，所以就存在这种情况，桶中一直有大量的可用令牌，这时进来的请求就可以直接拿到令牌执行，比如设置qps为100，那么限流器初始化完成一秒后，桶中就已经有100个令牌了，这时服务还没完全启动好，等启动完成对外提供服务时，该限流器可以抵挡瞬时的100个请求。所以，只有桶中没有令牌时，请求才会进行等待，最后相当于以一定的速率执行。
</p>
 
			<img src="https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/2452f2333b8a489929501bb950595791b4ecc2224903192c3f1656dfa652126cc11fec8c769d464b9c449f64f5c20dc1?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=2184951-b606dbcf328a8d84.webp&size=750" />
		 </div>
		<footer>
			<p>Design by <a href="http://cdcoder.cn" target="_blank">徐思润个人博客</a> </p>
			<p>备案号：<a href="/">蜀ICP备15014105号-1</a></p>
			<script type="text/javascript" src="https://s96.cnzz.com/z_stat.php?id=1277229191&web_id=1277229191"></script>
				<script src="../js/rainbow.min.js"></script>
			<script src="../js/java_h.js"></script>
		</footer>

	</body>
</html>
